package org.algorithm.dynamic;

public class DynamicProgram {

    public static void main(String[] args) {
        int[] w = {0, 1, 4, 3};
        int[] val = {0, 1500, 3000, 2000};


        dp(val, w, 4);
    }

    public static void dp(int[] val, int[] w, int weight) {


        int[][] v = new int[w.length][weight + 1];


        //第一行置为0
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0;
        }
        //第一列置为0
        for (int i = 0; i < v[0].length; i++) {
            v[0][i] = 0;
        }

        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[i].length; j++) {
                System.out.print(v[i][j] + "  ");
            }
            System.out.println();
        }

        System.out.println("======================================");

        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[i].length; j++) {

                /**
                 * 装不下当前物品时，上一个物品就是最优解
                 */
                if (w[i] > j) {
                    v[i][j] = v[i - 1][j];
                } else {// TODO: 2022/3/11 否则就是寻找最大的值，1.比较装不下时，和如果能装下时，剩下余量的值+当前物品 
                    v[i][j] = Math.max(v[i - 1][j], val[i] + v[i - 1][j - w[i]]);
                }
            }
        }

        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[i].length; j++) {
                System.out.print(v[i][j] + "  ");
            }
            System.out.println();
        }
    }


}
